package stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

public class LCR038 {
    public static void main(String[] args) {
        int[] a={73,74,75,71,69,72,76,73};
        LCR038Test01 lcr038Test01=new LCR038Test01();
        int[] b=lcr038Test01.dailyTemperatures(a);
        for(int n:b){
            System.out.print(n+" ");
        }
        System.out.println();
        LCR038Test02 lcr038Test02=new LCR038Test02();

        b=lcr038Test02.dailyTemperatures(a);
        for(int n:b){
            System.out.print(n+" ");
        }
        System.out.println();
        LCR038Test03 lcr038Test03=new LCR038Test03();

        b=lcr038Test03.dailyTemperatures(a);
        for(int n:b){
            System.out.print(n+" ");
        }

    }
}
/**
 * 解法一：纯暴力
 * */
class LCR038Test01{
        public int[] dailyTemperatures(int[] temperatures) {
            int length=temperatures.length;
            int[] ans=new int[length];

//            for(int i=0;i<length-1;i++){
//                int num=0;
//                int j;
//                for(j=i+1;j<length;j++){
//                    if(temperatures[i]>=temperatures[j])
//                        num++;
//                    else
//                        break;
//                }
//                if(j==length&num!=0) {
//                    ans[i] = 0;
//                }
//                else{
//                    ans[i]=num+1;
//                }
//
//            }
//            ans[length-1]=0;

            for(int i=0;i<length;i++){
                for(int j=i+1;j<length;j++){
                    if(temperatures[i]<temperatures[j]){
                        ans[i]=j-i;
                        break;
                    }
                }
            }

            return ans;
        }
}

/**
 * 解法二：单调栈维护下标，从底部到顶部，温度是由高到低，早找到高的把低的弹出去
 * */
class LCR038Test02{
    Deque<Integer> stack;
    public int[] dailyTemperatures(int[] temperatures) {
        stack=new ArrayDeque<>();
        int length=temperatures.length;
        int[] ans=new int[length];
        stack.push(0);
        for(int i=1;i<length;i++){

            while(!stack.isEmpty()&&temperatures[stack.peek()]<temperatures[i]){
                int preIndex=stack.pop();
                ans[preIndex]=i-preIndex;
            }
            stack.push(i);
        }
        return ans;
    }
}

/**
 * 解法二：单调栈维护下标，从底部到顶部，温度是由高到低，早找到高的把低的弹出去
 * 数组模拟优化栈
 *
 * */
class LCR038Test03{
    public int[] dailyTemperatures(int[] temperatures) {

        int length=temperatures.length;
        int[] stack=new int[length];
        int[] ans=new int[length];
        int top=0;
        for(int i=1;i<length;i++){
            int flag=0;
            while(temperatures[stack[top]]<temperatures[i]){
                int preIndex=stack[top];
                ans[preIndex]=i-preIndex;
                stack[top]=i;
                
            }
            stack[top++]=i;
        }
        return ans;
    }
}